<!DOCTYPE html>
<html>
	<head>
		<meta charset="utf-8">
		<title>双向链表</title>
	</head>
	<body>
	</body>
</html>
<script type="text/javascript">
	/*
	单向链表：
	  只能从头遍历到尾或者从尾遍历到头（一般从头到尾）
	  也就是链表相连的过程是单向的
	  实现的原理是上一个链表中有一个指向下一个的引用。
	单向链表的缺点：
	   我们可以轻松的到达下一个节点，但是回到前一个节点是很难的，但是，在时间开发过程中
	   经常会遇到需要回到上一个节点的情况
	   举个例子：假如一个文本编辑用链表来存储文本，每一行用一个String对象存储在链表的一个节点中。
	   当编辑器用户向下移动光标时，链表直接操作到下一个节点即可。但是当用于将光标向上移动呢？这个
	   时候为了回到上一个节点，我们可能需要从第一个开始，依次走到想要的节点。
	
	**/

	/*
	双向链表：
		即可以从头遍历到尾，又可以从尾遍历到头。
		也就是链表相连的过程是双向的，
		一个节点既有向前连接的引用，也有一个向后连接的引用。
		双向链表可以有效的解决单向链表中提到的问题
	双向链表的缺点：
		每次插入或删除某个节点时，需要处理四个引用，而不是2个，也就是实现起来困难一些。
		并且相当于单向链表，必然占用内存空间更大一些。
		但是这些缺点和我们使用起来的方便程度相比，是微不足道的、
	
	**/
	/**
	 * 双向链表的常见操作
	 * append(element):向列表尾部添加一个新的项
	 * insert(position,element):向列表的特定位置插入一个新的项
	 * get(position)：获取对应位置的元素
	 * indexOf(element):返回元素在列表中的索引。如果列表中没有该元素则返回-1
	 * update(position,element)：修改某个位置的元素
	 * removeAt(position)：从列表的特定位置移除一项
	 * remove(element):从列表中移除一项
	 * isEmpty():如果链表中不包含任何元素，返回true,如果链表长度大于0则返回false
	 * size()：返回链表包含的元素个数，与数组的length属性类型
	 * toString():由于列表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输入元素的值。
	 * forwardString():返回正方遍历的节点字符串形式
	 * backwardString():返回反向遍历的节点字符串形式
	 * */

	// 

	function DoublyLinkedList() {

		// 内部类创建节点
		function Node(data) {
			this.data = data;
			this.prev = null; 
			this.next = null;
		}
		// 包含属性
		this.head = null;
		this.tail = null;//上一个节点
		this.length = 0;
		// 常见方法的封装
		// 1.追加方法
		DoublyLinkedList.prototype.append = function(data) {

			// 1.创建新的节点
			var newNode = new Node(data)
			// 2.判断是否是第一个节点
			//2.添加节点
			//情况1：添加的是第一个节点
			if (this.length == 0) {
				this.tail = newNode
				this.head = newNode
				//情况2：添加的不是第一个节点
			} else {
				newNode.prev = this.tail
				this.tail.next = newNode
				this.tail = newNode
			}
			//3.length+1
			this.length += 1
		}
		// 2.链表转换成字符串形式
		DoublyLinkedList.prototype.toString = function() {
			return this.backwardString()
		}
		// 3.forwardString  向前
		DoublyLinkedList.prototype.forwardString = function() {
			// 1.定义变量
			var current = this.tail;
			var resultString = ''
			// 2.依次向前遍历，获取每一个节点
			while (current) {
				resultString += current.data + ' ';
				current = current.prev
			}
			return resultString
		}
		// 4.backwardString 向后
		DoublyLinkedList.prototype.backwardString = function() {
			// 1.定义变量
			var current = this.head;
			var resultString = ''
			// 2.依次向后遍历，获取每一个节点
			while (current) {
				resultString += current.data + ' ';
				current = current.next
			}
			return resultString
		}

		// 5.insert 插入
		DoublyLinkedList.prototype.insert = function(position, data) {
			// 1.越界判断
			if (position < 0 || position > this.length) return false
			// 2.根据data创建新的节点
			var newNode = new Node(data)

			// 3.判断原来的链表是否为空
			if (this.length == 0) {
				this.tail = newNode
				this.head = newNode
			} else {
				if (position == 0) { //5.1.判断position是否为0
					this.head.prev = newNode
					newNode.next = this.head
					this.head = newNode
				} else if (position == this.length) { //5.2.判断position == length 
					newNode.prev = this.tail
					this.tail.next = newNode
					this.tail = newNode
				} else {
					// 5.3.其他情况
					var current = this.head
					var index = 0
					while (index++ < position) {
						current = current.next
					}
					console.log('current',current)	
					// 修改指针
					newNode.next = current
					newNode.prev = current.prev
					current.prev.next = newNode
					current.prev = newNode
				}
			}
			// 4.length +=1
			this.length += 1
		}

		// 6.get 获取元素的位置信息
		DoublyLinkedList.prototype.get = function(position) {
			// 1.越界判断
			if (position < 0 || position >= this.length) return null;
			//  优化  根据position
			// 2.获取元素
			if (this.length / 2 > position) {
				var current = this.head;
				var index = 0;
				while (index++ < position) {
					current = current.next
				}
			
				return current.data
			} else {
				var current = this.tail;
				var index = this.length-1;
				console.log('index',index)
				console.log('position',position)
				//  4 
				while (index-- > position) {
					current = current.prev
				}
				return current.data
			}
		}

		// 7.indexOf 
		DoublyLinkedList.prototype.indexOf = function(data) {
			var current = this.head;
			var index = 0;
			while (current) {
				if (current.data == data) {
					return index
				}
				current = current.next
				index += 1
			}
			return -1
		}
		// 8.update  更新
		DoublyLinkedList.prototype.update = function(position, data) {
			// 1.越界判断
			if (position < 0 || position >= this.length) return false;
			// 2.寻找正确的节点
			if (this.length / 2 > position) {
				var current = this.head;
				var index = 0;
				while (index++ < position) {
					current = current.next
				}
				current.data = data
				return true
			} else {
				var current = this.tail;
				var index = this.length-1;
				console.log('index',index)
				console.log('position',position)
				//  4 
				while (index-- > position) {
					current = current.prev
				}
				current.data = data
				return true
			}
		}
		// 9.removeAt
		DoublyLinkedList.prototype.removeAt = function(position) {
			// 1.越界判断
			if (position < 0 || position >= this.length) return false;
			var current = this.head;
			if(this.length == 1){
				this.head = null;
				this.tail = null
			}else {
				// 9.1.判断删除的是否是第一个节点
				if(position == 0){
					this.head.next.prev = null;
					this.head = this.head.next
				}else if(position == this.length -1){
					current=this.tail
					this.tail.prev.next = null;
					this.tail = this.tail.prev
				}else{
				
					var index = 0;
					while(index++ < position){
						current = current.next
					}
					current.prev.next= current.next
					current.next.preve = current.prev
				}
			}
			// 3.length 减一
			this.length -=1
			return current.data
			
		}
		// 10 remove
		DoublyLinkedList.prototype.remove = function(data) {
			// 1.获取索引
			var index = this.indexOf(data)
			return this.removeAt(index)
			
		},
		//11.isEmpty 如果链表中不包含任何元素，返回true,如果链表长度大于0则返回false
		DoublyLinkedList.prototype.isEmpty = function(data) {
			return this.length==0?true:false
		}
		// 12.size
		DoublyLinkedList.prototype.size = function(data) {
			return this.length
		}
		// 13.获取链表的第一个元素
		DoublyLinkedList.prototype.getFirst = function(data) {
			return this.head.data
		}
		// 14.获取链表的最后一个元素
		DoublyLinkedList.prototype.getLast = function(data) {
			return this.tail.data
		}
		DoublyLinkedList.prototype.linkedList = function(){
			return this.head
		}
	}

	// 测试

	var list = new DoublyLinkedList()

	// 1.测试oppend
	list.append('aaa')
	list.append('bbb')
	list.append('ccc')
	// console.log('list.toString()',list.toString())
	// alert(list.toString())

	// 5.测试insert方法
	list.insert(1,'AAA')
	// list.insert(2,'CCC')
	// list.insert(4,'DDD')
    // console.log('list.toString()',list.linkedList())
	// alert(list)

	// 6.获取索引的值
	// alert(list.get(5))

	// 7.indexOf 获取索引
	// alert(list.indexOf('aaa'))
	
	// 8.update 更新
	// alert(list.update(0,'更新1'))
	// alert(list.update(5,'更新2'))
	// alert(list)
	
	// 9.removeAt  删除指定元素
	 
	// alert(list.removeAt(0))
	// alert(list)
	list.removeAt(3)
	// alert(list.removeAt(3))
	// alert(list)
	
	// 10.remove 删除
	// list.remove('aaa')
	// alert(list.remove('aaa'))
	// alert(list.toString())
	
</script>
